//数组中出现次数超过一半的数字: https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?
//思路一
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> map;
        int half = numbers.size() / 2;
        for (int i = 0; i < numbers.size(); i++) 
        {
            auto it = map.find(numbers[i]);
            //如果已经在map中，进行自增，如果不在，插入，首次出现
            if ( it != map.end() ) 
            {
                map[numbers[i]]++;
            } 
            else 
            {
                map.insert(make_pair(numbers[i], 1));
            }
            //自增或者插入一个，直接进行判定。注意，这里要考虑测试用例为{1}的情况
            //走到这里，对应的key val一定存在
            if (map[numbers[i]] > half) 
            {
                return numbers[i];
            }
        }
        //走到这里，说明没有找到
        return 0;
    }
};

//思路二
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        int target = numbers[numbers.size() / 2];
        int count = 0;
        for (int i = 0; i < numbers.size(); i++)   
        {
            if (target == numbers[i]) 
            {
                count++;
            }
        }
        if (count > numbers.size() / 2) 
        {
            return target;
        }
        return 0;
    }
};
//思路三
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.size() == 0) 
        {
            return 0;
        }
        //重点写一下
        //可以采取不同的数量进行抵消的思路
        int number = numbers[0];
        int times = 1;
        for (int i = 1; i < numbers.size(); i++) 
        {
            if (times == 0) 
            { 
                //如果当前times是0，说明之前的不同抵消完了
                number = numbers[i];
                times = 1;
            } 
            else if (numbers[i] == number) 
            {
                times++;
            } 
            else 
            {
                times--;
            }
        }
        //如果输入本身满足条件，则times一定>0, 并且number保存的就是准目标，但是还需要确认
        int count = 0;
        for (int i = 0; i < numbers.size(); i++) 
        {
            if (numbers[i] == number) 
            {
                count++;
            }
        }
        return count > numbers.size() / 2 ? number : 0;
    }
};